public class Sort {
//    public static void insertSort(int[] arr) {
//        for (int i = 1; i < arr.length; i++) {
//            int ret = arr[i];
//            int j = i - 1;
//            for (; j >= 0; j--) {
//                if (arr[j] < ret) {
//                    arr[j + 1] = arr[j];
//                } else {
//                    break;
//                }
//            }
//            arr[j + 1] = ret;
//        }
//    }

    public static void insertSort(int[] array){
        // write code  here
        for (int i = 1; i < array.length; i++) {
            int ret = array[i];
            int j = i-1;
            for (; j >= 0; j--) {
                if(array[j] > ret) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = ret;

        }
    }


        // 希尔排序
      public static void shellSort(int[] array){
        // write code  here
          int gap = array.length / 2;
          while(gap > 0) {
              insertSort2(array,gap);
              gap /=2;
          }
    }

    public static void insertSort2(int[] array,int gap){
        // write code  here
        for (int i = gap; i < array.length; i++) {
            int ret = array[i];
            int j = i-gap;
            for (; j >= 0; j-=gap) {
                if(array[j] > ret) {
                    array[j+gap] = array[j];
                }else {
                    break;
                }
            }
            array[j+gap] = ret;

        }
    }


    public static void fasts(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int min = i;
            for (int j = i+1; j < arr.length; j++) {
                if(arr[min] < arr[j]) {
                    min = j;
                }
            }
            int tem = arr[i];
            arr[i] = arr[min];
            arr[min] = tem;
        }
    }


}